#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    static vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.size() == 0)
            return { -1, -1 };

        int begin = -1, end = -1;

        int left = 0, right = nums.size() - 1;
        while (left < right)
        {
            int midi = (right - left) / 2 + left;
            if (nums[midi] < target)
                left = midi + 1;
            else
                right = midi;
        }
        begin = left;
        if (nums[begin] != target)
            return { -1, -1 };

        left = 0, right = nums.size() - 1;
        while (left < right)
        {
            int midi = (right - left + 1) / 2 + left;
            if (nums[midi] <= target)
                left = midi;
            else
                right = midi - 1;
        }
        end = left;
        return { begin, end };
    }
};

int main()
{
    std::vector<int> nums = { 5, 7, 7, 8, 8, 10 };
    auto ret = Solution::searchRange(nums, 8);
    std::cout << ret[0] << " " << ret[1] << std::endl;
    return 0;
}

